// m

// 一条环路上有N个加油站，第i个加油站有gas[i]升汽油
// 现在有一辆无限容量的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升，如果汽车上携带的油不够cost[i]，则无法从第i个加油站开往第i+1个加油站
// 现在从其中一个加油站开始出发，且出发时油箱为空，如果能绕环路行驶一周，则返回出发时加油站的编号，否则返回-1

// 解题思路： 贪心算法
// 1. 如果加油站提供的油总和大于等于消耗的汽油量，则必定可以绕环路行驶一周
// 2. 假设先不考虑油量为负的情况，从第0个加油站出发，环形一周，记录下汽油量gas[i]和cost[i]差值总和sum_diff,同时记录下邮箱剩余油量的最小值min_sum
// 3. 如果差值总和sum_diff < 0,则无论如何都不能环形一周
// 4. 如果min_sum >= 0, 则行驶过程中油箱始终有油，则可以从0个加油站出发环形一周
// 5. 如果min_sum < 0, 则行驶过程中油箱油不够了，那么考虑更换开始的起点
//      1. 从右至左遍历，计算汽油量gas[i]和cost[i]的差值，看哪个加油站能将min_sum填平，如果最终达到min_sum >= 0,则说明从该点开始出发，油箱中的油始终不为空，则返回该点下标
//      2. 如果找不到返回-1

function canCompleteCircuit(gas, cost) {
    let sum_diff = 0, min_sum = Infinity
    for (let i = 0; i < gas.length; i++) {
        sum_diff += gas[i] - cost[i]
        min_sum = Math.min(min_sum, sum_diff)        
    }

    if (sum_diff < 0) {
        return -1
    }
    if (min_sum >= 0) {
        return 0
    }
    for (let i = gas.length - 1; i >= 0; i--) {
        min_sum += gas[i] - cost[i]
        if (min_sum >= 0) {
            return i
        }        
    }
    return -1
}

let gas = [1,2,3,4,5], cost = [3,4,5,1,2]
console.log(canCompleteCircuit(gas, cost))